// 解题思路
// 定义 DP 状态：
// 设 dp[j] 表示 背包容量 j 时的最大价值。
// 状态转移方程：
// 遍历物品 i，对于每个物品有两种选择：
// 不选它：dp[j] 不变。
// 选它：dp[j] = dp[j - weights[i]] + values[i]（即在容量 j - weights[i] 时选入 values[i]）。
// 取最大值：
// dp[j]=max(dp[j],dp[j−weights[i]]+values[i])
// 遍历顺序：
// 先遍历物品，再从 背包容量 W 逆序遍历，防止重复计算。
/**
 * @param {number[]} weights - 物品体积数组
 * @param {number[]} values - 物品价值数组
 * @param {number} W - 背包容量
 * @return {number} - 最大总价值
 */
function knapsack(weights, values, W) {
    const dp = new Array(W + 1).fill(0)
    for (let i = 0; i < weights.length; i++) {
        for (let j = W; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], (dp[j - weights[i]] + values[i]))
        }
    }
    return dp[W]
}
console.log(knapsack([4, 2, 3], [4, 2, 3], 5)); // 输出: 4